Analysis of Two LeetCode Questions
Posted on 19 June, 2018 in Algorithm
Hello there,
We are going to analyze two interesting questions from LeetCode.
Unique Paths
We will investigate this question in this section. Therefore, instead of directly jumping into solution, read and try to solve by yourself.
We will solve it by using permutation. Let's call starting point (0,0) for the robot and (m-1,n-1) for the end mark. Therefore we, as a robot, need to go n-1 times down and m-1 times right. The ordering of these right and down does matter. Hence, we just need to find how do we order them.
For example, let call n is equal to 5 and m is equal to 3. We have a 3x5 grid. We need to go 2 times right and 4 four times down for reaching the end mark. We can go as follows
RRDDDD or DRDRDD or RDDDDR and many more ....
All of these paths(different ordering of m-1 times R and n-1 times D) in the above will give us the same output. However, each of these paths is unique. We just need to find how do we order R's and D's. This is the part where permutation comes into play. Following formula gives us the how many different ordering, that we can get from m-1 times R and n-1 times D.class Solution:
def fac(self, k):
return k*self.fac(k-1) if k > 1 else 1
def uniquePaths(self, m, n):
return int(self.fac(m+n-2) / (self.fac(m-1)*self.fac(n-1)))
We are calculating factorial of (m+n-2). Therefore, this algorithm runs in O(n+m) and takes O(1) space.
Another solution would be BFS. We can just go in each node and keep track of paths. Nevertheless, we will not solve it by using BFS. If you like to challenge yourself, go for it.
Max Area of Island
We will investigate this question in this section. Therefore, instead of directly jumping into solution, read and try to solve by yourself.
This question asks the largest number of consecutive ones in a matrix. Hence, we need to implement BFS method.
We shall start BFSing when the number in the matrix is 1. We will find every consecutive one and count them by using BFS. The important part in here is changing array while running BFS. If we don't change visited ones with zeros, we will calculate same consecutive ones again and again. Changing visited ones with zeros prevents this situation.
class Solution {
public:
// We need to pass the address of the grid for changing visited ones.
int bfs(vector<vector<int>>& grid, int iInput, int jInput){
queue<pair<int,int>> q;
q.push(make_pair(iInput,jInput));
grid[iInput][jInput] = 0;
int counter = 0;
// While q is not empty try to go left, right, bottom and up.
while(!q.empty()){
pair<int, int> currentNode = q.front();
q.pop();
int i = currentNode.first, j = currentNode.second;
counter++;
// Try to go up
if(i-1 >= 0)
if(grid[i-1][j] == 1)
q.push(make_pair(i-1,j)), grid[i-1][j] = 0;
// Try to go down
if(i+1 < grid.size())
if(grid[i+1][j] == 1)
q.push(make_pair(i+1,j)), grid[i+1][j] = 0;
// Try to go left
if(j-1 >= 0)
if(grid[i][j-1] == 1)
q.push(make_pair(i,j-1)), grid[i][j-1] = 0;
// Try to go right
if(j+1 < grid[i].size())
if(grid[i][j+1] == 1)
q.push(make_pair(i,j+1)), grid[i][j+1] = 0;
}
return counter;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int maxVal = 0;
// We need to run bfs function if the number in the matrix is one.
for(int i = 0;i<grid.size();i++)
for(int j=0;j<grid[i].size();j++)
if(grid[i][j] == 1)
maxVal = max(maxVal, bfs(grid, i, j));
return maxVal;
}
};
It seems like we have many for loops. However, we are visiting all numbers inside of the matrix. Therefore, this algorithm runs in O(n*m), which is all nodes inside the matrix.